perm filename V2I.IN[TEX,DEK] blob
sn#285505 filedate 1977-05-28 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00005 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 folio 397 galley 1
C00020 00003 folio 403 galley 2
C00038 00004 folio 407 galley 3
C00059 00005 folio 411 galley 4
C00081 ENDMK
C⊗;
folio 397 galley 1
0 {U31}1|'{H10L12M29}W58320#Computer Programming!(Knuth/A-W)!f
2 . 397!Ch. 4!g.|91(c)|'{A24}|∨4|∨.|∨4|9|∨R|∨A|∨D|∨I|∨X|9|∨C|∨
5 O|∨N|∨V|∨E|∨R|∨S|∨I|∨O|∨N|'{A12}If men had invented
10 arithmetic by counting with their two _sts or
18 their eight _ngers, instead of their ten ``digits,''
26 we would never have to worry about writing binary-decimal
35 conversion routines. (And we would perhaps never
42 have learned as much about number systems.) In
50 this section, we shall discuss the conversion
57 of numbers from positional notation with one
64 radix into positional notation with another radix;
71 this process is, of course, most important on
79 binary computers when converting decimal input
85 data into binary form, and converting binary
92 answers into decimal form.|'|≡A|≡.|9|≡T|≡h|≡e
97 |≡f|≡o|≡u|≡r |≡b|≡a|≡s|≡i|≡c |≡m|≡e|≡t|≡h|≡o|≡d|≡s|≡.|9|4Bin
99 ary-decimal conversion is one of the most machine
107 dependent operations of all, since engineers
113 keep inventing di=erent ways to provide for it
121 in the computer hardware. Therefore we shall
128 discuss only the general principles involved,
134 from which a programmer can select the procedure
142 most well suited to his machine.|'!|4|4|4|4We
149 shall assume that only nonnegative numbers enter
156 into the conversion, since the manipulation of
163 signs is easily accounted for.|'!|4|4|4|4Let
169 us assume that we are converting from radix |εb
178 |πto radix |εB. |π(The methods can also be generalized
187 to mixed radix notations, as shown in exercises
195 1 and 2.) Most cr*?*?!|4|4|4|4Let us assume that
203 we are converting from radix |εb |πto radix |εB.
212 |π(The methods can also be generalized to mixed
220 radix notations, as shown in exercises 1 and
228 2.) Most radix conversion routines are based
235 on multiplication and division, using one of
242 the following four schemes:|'{A6}!|4|4|4|41)|9Conversion
247 of integers (radix point at the right).|'{A12}!Method
255 (1a) |εDivision by B (|πusing radix |εb |πarithmetic).
263 Given an integer number |εu, |πwe obtain its
271 radix |εB |πrepresentation |ε(U|βM|4.|4.|4.|4U|β1U|β0)|βB
275 |πas follows:|'{A9}|h|εU|β2|4|∂α=↓|4|"l|"lu/B|"L/B|"L|πmod|4
277 |εB|E|n|;| U|β0|4|Lα=↓|4u|4|πmod|4|εB>{A6}| U|β1|4|Lα=↓|4|"l
279 u/B|"L|πmod|4|εB>{A6}| U|β2|4|Lα=↓|4|"l|"lu/B|"L/B|"L|πmod|4
280 |εB>{A24}|πetc., stopping when |"l.|4.|4.|4|"l|"l|εu/B|"L/B|
284 "L|4.|4.|4.|4/B|"Lα=↓0.|'{A12}|π!Method (1b)
287 |εMultiplication by b (|πusing radix |εB |πarithmetic).
294 If |εu |πhas the radix |εb |πrepresentation |ε(u|βm|4.|4.|4.
301 |4u|β1u|β0)|βb, |πwe can use radix |εB |πarithmetic
308 to evaluate the polynomial |εu|βmb|gm|4α+↓|4αo↓|4αo↓|4αo↓|4α
312 +↓|4u|β1b|4α+↓|4u|β0α=↓u |πin the form|'{A9}|ε{H12}({H10}(.|
316 4.|4.|4(u|βmb|4α+↓|π!|4|4|4|42)|9Conversion of
318 fractions (radix point at the left). Note that
326 it is often impossible to express a terminating
334 radix |εb |πfraction (|ε0.u|βα_↓|β1u|βα_↓|β2|4.|4.|4.|4u|βα_
337 ↓|βm)|βb |εexactly |πas a terminating radix |εB
344 |πfraction |ε(0.U|βα_↓|β1U|βα_↓|β2|4.|4.|4.|4U|βα_↓|βM)|βB.
346 |πFor example, the fraction |f1|d310|) has the
353 in_nite binary representation (0.0|40011|40011|40011|4.|4.|4
356 .)|β2. Therefore methods of rounding the result
363 to |εM |πplaces are sometimes of interest.|'{A12}!Method
371 (2a) |εMultiplication by B |π(using radix |εb
378 |πarithmetic). Given a>fractional number |εu,
384 |πwe obtain successive digits of its radix |εB
392 |πrepresentation>|ε(.U|βα_↓|β1U|βα_↓|β2|4.|4.|4.)|βB
394 |πas follows:|'{A9}|h|εU|βα_↓|β3|4|∂α=↓|4|"l|¬A|¬AuB|¬SB|¬SB
396 |"L|E|n|;| U|βα_↓|β1|4|Lα=↓|4|"luB|"L>{A4}| U|βα_↓|β2|4|Lα=↓
398 |4|"l|¬AuB|¬SB|"L>{A4}| U|βα_↓|β3|4|Lα=↓|4|"l|¬A|¬AuB|¬SB|¬S
399 B|"L>{A24}|πwhere |ε|¬Ax|¬S |πdenotes |εx |πmod
405 1|4α=↓|4|εx|4α_↓|4|"lx|"L. |πIf it is desired
410 to round the result to |εM |πplaces, the computation
419 can be stopped after |εU|βα_↓|βM |πhas been calculated,
427 and |εU|βα_↓|βM |πshould be increased by unity
434 if |ε|¬A.|4.|4.|¬A|¬AuB|¬S|4.|4.|4.|4B|¬S |πis
437 greater than |f1|d32|). (Note, however, that
443 this may cause a number of carries to occur,
452 which must be incorporated into the answer using
460 radix |εB |πarithmetic. Therefore it would be
467 simpler to add the constant |f1|d32|)|εB|gα_↓|gM
473 |πto the original number |εu |πbefore the calculation
481 begins, but this may lead to a terribly incorrect
490 answer when |f1|d32|)|εB|gα_↓|gM |πcannot be
495 represented exactly as a radix |εb |πnumber inside
503 the computer. Note further that it is possible
511 for the answer to round up to (1.00|4.|4.|4.|40)|ε|βB,
519 |πif |εb|gm|4|¬R|42B|gM.)|'{A12}|π!Method (2b)
523 |εDivision by b (|πusing radix |εB |πarithmetic).
530 If |εu |πhas the radix |εb |πrepresentation |ε(0.u|βα_↓|β1u|
537 βα_↓|β2|4.|4.|4.|4u|βα_↓|βm)|βb, |πwe can use
541 radix |εB |πarithmetic to evaluate |εu|βα_↓|β1b|gα_↓|g1|4α+↓
546 |4u|βα_↓|β2b|gα_↓|g2|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4u|βα_↓|βmb|gα
546 _↓|gm |πin the form|'{A9}{H12}|ε({H10}(.|4.|4.|4(u|βα_↓|βm/b
550 |4α+↓|4u|β1|βα_↓|βm)/b|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4u|βα_↓|β2)/
550 b|4α+↓|4u|βα_↓|β1{H12}){H10}/b.|;{A9}{H10L12M29}|πCare
552 should be taken to control errors which might
560 occur due to truncation or rounding in the division
569 by |εb; |πthese are often negligible, but not
577 always.|'!|4|4|4|4To summarize, Methods (1a),
582 (1b), (2a), and (2b) give us two choices for
591 a conversion process, depending on whether our
598 number is an integer or a fraction. And it is
608 certainly possible to convert between integers
614 and fractions by multiplying or dividing by an
622 appropriate power of |εb |πor |εB; |πtherefore
629 there are at least four methods to choose from
638 when trying to do a conversion.|'{A12}|≡B|≡.|9|≡S|≡i|≡n|≡g|≡
644 l|≡e |≡p|≡r|≡e|≡c|≡i|≡s|≡i|≡o|≡n |≡c|≡o|≡n|≡v|≡e|≡r|≡s|≡i|≡o
646 |≡n|≡.|9|4To illustrate these four methods, let
652 us assume that |¬m|¬i|¬x is a binary computer,
660 and suppose that we want to convert a binary
669 integer |εu |πto a decimal integer, that is,
677 |εb|4α=↓|42 |πand |εB|4α=↓|410. |πMethod (1a)
682 could be programmed as follows:|'{A9}{H9L11M29}|h|ε|∂|¬1|¬h!
687 |∂|¬e|¬n|¬t|¬a!|∂|¬a|¬n|¬s|¬w|¬e|¬r|¬,|4|1|¬1!!|∂(rA,|4rX)|4
687 |¬M|4(|"lrAX/10|"L,|4|1rAX|4|πmod|410).|E|n|;
688 |L|L|¬e|¬n|¬t|¬1|L|¬0|LSet|4|1|εj|4|¬L|40.>|L|L|¬l|¬d|¬x|L|¬
689 u>|L|L|¬e|¬n|¬t|¬a|L|¬0|¬|πSet|4|1rAX|4|¬L|4|εu.>
691 |L|¬1|¬h|L|¬d|¬i|¬v|L|≤$|¬1|¬0|≤$|L|π(rA,|4rX)|4|¬L|4(|"lrAX
691 /10|"L,|4rAX|4mod|410).>|L|L|¬s|¬t|¬x|L|¬a|¬n|¬s|¬w|¬e|¬r|¬,
692 |4|¬1|L|εU|βj|4|¬L|4|πrX.>|L|L|¬i|¬n|¬c|¬1|L|¬1|L|εj|4|¬L|4j
693 |4α+↓|41.>|L|L|¬s|¬r|¬a|¬x|L|¬5|L|πrAX|4|¬L|4rA.>
695 |L|L|¬j|¬x|¬p|L|¬1|¬b|LRepeat|4|1until|4|1result|4|1is|4|1ze
695 ro.|J!(1)>{A9}{H10L12M29}This requires 18|εM|4α+↓|44
699 |πcycles to obtain |εM |πdigits.|'!|4|4|4|4The
705 above method used division by 10, Method (2a)
713 uses |εmultiplication |πby 10, so it might be
721 a little faster. In order to use Method (2a),
730 we must deal with fractions, and this leads to
739 an interesting situation. Let |εw |πbe the word
747 size of the computer, and assume that |εu|4|¬W|410|gn|4|¬W|4
754 w. |πWith a single division we can _nd |εq |πand
764 |εr, |πwhere|'{A9}|εwuα=↓10|gpq|4α+↓|4r,!!0|4|¬E|4r|4|¬W|410
766 |gp,|J!(2)|;{A9}|πNow if we apply Method (2a)
773 to the fraction |ε(q|4α+↓|41)/w, |πwe will obtain
780 the digits of |εu |πfrom left to right, in |εn
790 |πsteps, since|'{A9}|ε|↔d10|gn|4|(q|4α+↓|41|d2w|)|↔f|4α=↓|4|
792 ↔du|4α+↓|4|(10|gn|4α_↓|4r|d2w|)|↔f|4α=↓|4u.|J!(3)|;
793 {A9}|π(This idea is due to P. A. Samet, |εSoftware#Practice
802 and Experience |≡1 (1971), 93<96.)|'|π!|4|4|4|4Here
808 is the corresponding |¬m|¬i|¬x program:|'{A9}{H9L11M29}|h|n|
813 ∂|¬2|¬h!|∂|¬j|¬i|¬n|¬n!|∂|¬a|¬n|¬s|¬w|¬e|¬r|¬,|4|1|¬1!|∂Now|
813 4|1imagine|4|1radix|4|1point|4|1at|4|1left,|4|1rA|4α=↓|4|εx.
813 |E|n|;|L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|L|πEnsure|4|1over⊗ow|4|1is
814 |4|1o=>|L|L|¬l|¬d|¬a|Lu>|L|L|¬l|¬d|¬x|L|≤$|¬1|¬0|gn|≤$|LrAX|
816 4|¬L|4|εwu|4α+↓|410|ε|gn.>|π|L|L|¬d|¬i|¬v|L|≤$|¬1|¬0|gn|≤$|L
817 rA|4|¬L|4|εq|4α+↓|41,|4|πrX|4|¬L|4|εr.>|L|L|¬j|¬o|¬v|L|¬e|¬r
818 |¬r|¬o|¬r|L|πJump|4|1if|4|1|εu|4|¬R|410|gn.>|L|L|¬e|¬n|¬t|¬1
819 |L|πn<|¬1|LSet|4|1|εj|4|¬L|4nα_↓1.>|L|¬2|¬h|L|¬m|¬u|¬l|L|≤$|
820 ¬1|¬0|≤$|L|πNow|4|1imagine|4|1radix|4|1point|4|1at|4|1left,|
820 4|1rA|4α=↓|4|εx.>|L|L|π|¬s|¬t|¬a|L|¬a|¬n|¬s|¬w|¬e|¬r|¬,|4|¬1
821 |LSet|4|1|εU|βj|4|¬L|4|"l10x|"L.>|L|L|¬s|¬l|¬a|¬x|L|¬5|Lx|4|
822 ¬L|4|¬A10x|¬S.>|π|L|L|¬d|¬e|¬c|¬1|L|¬1|L|εj|4|¬L|4j|4α_↓|41.
823 >|L|L|π|¬j|¬i|¬n|¬n|L|¬2|¬b|LRepeat|4|1for|4|1|εn|4|¬Q|4j|4|
824 ¬R|40.|J!(4)>{A9}{H10L12M29}|πThis slightly longer
828 routine requires |ε16n|4α+↓|419 |πcycles, so
833 it is a little faster than (1) if |εn|4α=↓|4M|4|¬R|48;
842 |πwhen leading zeroes are present, (1) will be
850 faster.|'!|4|4|4|4Program (4) as it stands cannot
857 be used to convert integers |εu|4|¬R|410|gm |πwhen
864 |ε10|gm|4|¬W|4w|4|¬W|410|gm|gα+↓|g1, |πsince
866 we would need to take |εn|4α=↓|4m|4α+↓|41. |πIn
873 this case we can obtain the leading digit of
882 |εu |πby computing |ε|"lu/10|gm|"L; |πthen |εu
888 |πmod 10|ε|gm |πcan be converted as above with
896 |εn|4α=↓|4m.|'|π!|4|4|4|4The fact that the answer
902 digits are obtained from left to right may be
911 an advantage in some applications (e.g., when
918 typing out the answer one digit at a time). Thus
928 we see that a fractional method can be used for
938 conversion of integers, although the use of inexact
946 division makes a little bit of numerical analysis
954 necessary.|'!|4|4|4|4A modi_cation of Method
959 (1a) can be used to avoid division by 10, by
969 replacing it with two multiplications. It is
976 worth mentioning this modi_cation here, because
982 radix conversion is often done by small ``satellite''
990 computers which have no division capability.
996 If we let |εx |πbe an approximation to |f1|d310|),
1005 so that |f1|d310|)|4|¬W|4x|4|¬W|4|f1|d310|)|4α+↓|41/|εw,
1008 |πit is easy to prove (see exercise 7) that |ε|"lux|"L|4α=↓|
1017 4|"lu/10|"L |πor |ε|"lu/10|"L|4α+↓|41, |πso long
1022 as |ε0|4|¬E|4u|4|¬W|4w. |πTherefore, if we compute
1028 |εu|4α_↓|410|"lux|"L, |πwe will be able to determine
1035 the value of |ε|"lu/10|"L:|'{A9}|ε|"lu/10|"L|4α=↓|4|↔A|(|"lu
1039 x|"L,!|4|4|4|4!!|πif!!|εu|4α_↓|410|"lux|"L|4|¬R|40;|d5|"lux|
1039 "L|4α_↓|41,!!|πif!!|εu|4α_↓|410|"lux|"L|4|¬W|40.|)|J!(5)|;
1040 |Hβ*?*?*?*?
folio 403 galley 2
2301 {U0}{H10L1
2309 2M29}|π58320#Computer Programming!(Knuth/Addison/Wesley)!f.
2311 403!ch. 4!g. 2(c)|'{A6}This procedure simultaneously
2317 determines |εu |πmod|410. A |¬m|¬i|¬x program
2323 for conversion using this idea appears in exercise
2331 8; it requires about 33 cycles per digit.|'!|9|7The
2340 procedure represented by (5) can be used e=ectively
2348 even if the computer has no built-in multiplication
2356 instruction, since multiplication by 10 consists
2362 of two shifts and one addition (10|4α=↓|42|g3|4α+↓|42),
2369 and multiplication by |f1|d310|) can also be
2376 done by combining a few shifting and adding operations
2385 judiciously (see exercise 9).|'!|9|7Method (1b)
2391 could also be used to convert from binary to
2400 decimal, but to do this we need to simulate doubling
2410 in a |εdecimal |πnumber system. This idea is
2418 generally most suitable for incorporation into
2424 computer hardware; however, it is possible to
2431 program the doubling process for decimal numbers,
2438 using binary addition, shifting, and extraction
2444 (``logical |¬a|¬n|¬d'' on each bit in the register),
2452 as shown in Table 1.|'{A22}{H8L10}|∨T|∨a|∨b|∨l|∨e
2458 |∨1|;{A4}{H9L11}DOUBLING A BINARY-CODED DECIMAL
2463 NUMBER|;{A6}|∂!!!!!!!|9|3|∂!!!!!!!!!!!!!!!!!!|∂!!!!!!!!!!!!!
2464 |∂|E|;|>!|6|εOperation|'General form!!|;Example|;
2470 >{A2}|>|π1.|9Given|'!|9|εu|β1|2u|β2|2u|β3|3u|β4|2|9u|β5|2u|β
2473 6|2u|β7|2u|β8|2|9u|β9|2|9u|β1|β0|2u|β1|β1|2u|β1|β2|'
2474 !|10011|90110|91001|4α=↓|43|96|99|'>|>!|6|πnumber|'
2478 >|>2.|9Add 3 to|'!|9|εv|β1|2v|β2|2v|β3|2v|β4|2|9v|β5|2v|β6|2
2483 v|β7|2v|β8|2|9v|β9|2|9v|β1|β0|2v|β1|β1|2v|β1|β2|'
2484 !|10110|91001|91100|'>|>!|6|πeach digit|'>|>3.|9Shift
2492 left|'|εv|β1|2|9v|β2|2v|β3|2v|β4|2v|β5|2|9v|β6|2v|β7|2v|β8|2
2493 v|β9|2|9v|β1|β0|5v|β1|β1|2v|β1|β2|20|'0|91101|90011|91000|'
2495 >|>!|6|πone|'>|>4.|9Extract low|'|εv|β1|2|90|4|40|4|40|4|4v|
2502 β5|2|90|4|40|4|40|4|4v|β9|2|90|9|50|9|50|9|50|'
2503 0|90001|90001|90000|'>|>!|6|πbit|'>|>5.|9Shift
2510 right|'!|90|4|4|εv|β1|20|4|40|9|4|40|4|4v|β5|20|4|40|4|4|90|
2511 4|4|9v|β9|4|40|9|50|'!|10000|90100|90100|'>|>
2515 !|6|πtwo|'>|>6.|9Shift right|'!|90|4|4v|β1|2v|β1|20|4|4|90|4
2520 |4v|β5|2v|β5|20|4|4|90|4|4|9v|β9|4|4v|β9|4|40|'
2521 !|10000|90110|90110|'>|>!|6one and add|'>|>7.|9Add
2530 result|'|≤⊂!|≤⊂|9|≤⊂|9|≤⊂|9|≤⊂|9|9|≤⊂|9|≤⊂|9|≤⊂|9|≤⊂|9|9|≤⊂|
2531 9|9|≤⊂|9|6|≤⊂|1|9|50|'0|91101|91001|91110|'>|>
2535 !|6of step 3|'>|>8.|9Subtract 6|'|εy|β1|2|9y|β2|2y|β3|2y|β4|
2542 2y|β5|2|9y|β6|2y|β7|2y|β8|2y|β9|9|2y|β1|β0|2y|β1|β1|2y|β1|β2
2542 |20|'0|90111|90011|91000|4α=↓|47|93|98|'>|>!|6|πfrom
2547 each|'>{A25}{H10L12M29}|π!|9|7Another relaed
2551 idea is to keep a table of the powers of two
2562 in decimal form, and to add the appropriate powers
2571 together by simulating decimal addition. A survey
2578 of such bit-manipulation techniques appears in
2584 Section 7.1.|'!|9|7Finally, even Method (2b)
2590 can be used for the conversion of binary integers
2599 to decimal integers. We can _nd |εq as in (2),
2609 and then we can simulate the decimal division
2617 of |εq|4α+↓|41 |πby |εw, |πusing a ``halving''
2624 process (exercise 10) which is similar to the
2632 doubling process just described, and retaining
2638 only the _rst |εn |πdigits to the right of the
2648 radix point in the answer. In this situation,
2656 Method (2b) does not seem to o=er advantages
2664 over the other three methods already discussed,
2671 but we have con_rmed the remark made earlier
2679 that at least four distinct methods are available
2687 for converting integers from one radix to another.|'
2695 {A6}This method changes each individual digit
2701 |εd |πinto |ε{H12}({H10}(d|4α+↓|43)|4α⊗↓|42|4α+↓|40)|4α_↓|46
2703 |4α=↓|42d |πwhen |ε0|4|¬E|4d|4|¬E|44, |πand into
2708 |ε{H12}({H10}(d|4α+↓|43)|4α⊗↓|42|4αt↓|46{H12}){H10}|4α_↓|46|
2708 4α=↓|4(2d|4α_↓|410)|4α+↓|42|g4 |πwhen |ε5|4|¬E|4d|4|¬E|4q;
2711 |πand that is just what is needed to double decimal
2721 numbers encoded with 4 bits per digit.|'{A6}!|9|7Method
2729 (1b) is the most practical method for decimal-to-binary
2737 conversion in the great majority of cases. Here
2745 it is in |¬m|¬i|¬x code, assuming that there
2753 are at least two digits in the number |ε(u|βm|4.|4.|4.|4u|β1
2761 u|β0)|β1|β0 |πbeing converted:|'{A8}{H9L11}|h|¬1|¬h!|∂|¬s|¬l
2764 |¬a|¬x!|¬i|¬n|¬p|¬u|¬t|¬,|¬1!!|∂Repeat for |εm|4|¬Q|4j|4|¬Q|
2766 40.|E|n|;|π|L|L|¬e|¬n|¬t|¬1|L|¬m|≤*/|¬1|LSet |εj|4|¬L|4m|4α_↓
2768 |41.>|L|L|π|¬l|¬d|¬a|L|¬i|¬n|¬p|¬u|¬t|≤%|¬m|LSet
2770 |εU|4|¬L|4u|βm.>|π|L|¬1|¬h|L|¬m|¬u|¬l|L|≤$|¬1|¬0|≤*/>
2772 |L|L|¬s|¬l|¬a|¬x|L|¬5>|L|L|¬a|¬d|¬d|L|¬i|¬n|¬p|¬u|¬t|¬,|¬1|L
2773 |εU|4|¬L|410U|4α+↓|4u|βj.>|π|L|L|¬d|¬e|¬c|¬1|L|¬1>
2775 |L|L|¬j|¬i|¬n|¬n|L|¬1|¬b|LRepeat for |εm|4|¬Q|4j|4|¬R|40.|J!
2777 (6)>{A10}{H10L12}|πNote again that adding and
2783 shifting may be substituted for multiplication
2789 by 10.|'!|9|7A trickier but perhaps faster method,
2797 which uses about lg|4|εm |πmultiplications, extractions,
2803 and additions instead of |εm |πmultipliations
2809 and additions, is described in exercise 19.|'
2816 !|9|7For the conversion of decimal fractions
2822 (0.|εu|βα_↓|β1u|βα_↓|β2|4.|4.|4.|4u|βα_↓|βm)|β1|β0,
2823 |πwe can use Method (2b), or, more commonly,
2831 we can convert the integer |ε(u|βα_↓|β1u|βα_↓|β2|4.|4.|4.|4u
2836 |βα_↓|βm)|β1|β0 |πby Method (1b) and then divide
2843 by 10|ε|gm.|'{A12}|π|≡C|≡.|9|≡H|≡a|≡n|≡d |≡c|≡a|≡l|≡c|≡u|≡l|
2846 ≡a|≡t|≡i|≡o|≡n|≡.|9|4Occasionally, it is necessary
2850 for computer programmers to convert numbers by
2857 hand, and since this is a subject not yet taught
2867 in elementary schools, it may be worth while
2875 to examine it brie⊗y here. There are very simple
2884 pencil-and-paper methods for converting between
2889 decimal and octal notations, and these methods
2896 are easily learned, so they ought to be more
2905 widely known.|'{A12}|εConverting octal integers
2910 to decimal.|9|4|πThe simplest conversion is from
2916 octal to decimal; this technique was apparently
2923 _rst published by Walter Soden, |εMath. Comp.
2930 |≡7 (1953), 273<274. |πTo do the conversion,
2937 write down the given octal number; then at the
2946 |εk|πth step, double the |εk |πleading digits
2953 using decimal arithmetic, and subtract this from
2960 the |εk|4α+↓|41 |πleading digits using decimal
2966 arithmetic. The process terminates in |εn|4α_↓|41
2972 |πsteps if the given number has |εn |πdigits.
2980 It is a good idea to insert a radix point to
2991 show which digits are being doubled, as shown
2999 in the examples given here, in order to prevent
3008 embarrassing mistakes.|'{A6}|≡E|≡x|≡a|≡m|≡p|≡l|≡e
3011 |≡1|≡.|9|4Convert (5325121)|β8 to decimal.|'{A9}!|9|∂5|2.|23
3015 |92|95|91|92|91|'| |→α_↓|91|90>{B2}!|9##|'|L4|93|2.|22|95|91
3018 |92|91>| |→α_↓|9|9|1|98|96>{B2}!|9##|'|L3|94|96|2.|25|91|92|
3021 91>| |→α_↓|9|9|1|96|99|92>{B2}!|9####|'|L2|97|97|93|2.|21|92
3024 |91>| |→α_↓|9|9|1|95|95|94|96>{B2}!|9####|'|L2|92|91|98|95|2
3027 .|22|91>| |→α_↓|9|9|1|94|94|93|97|90>{B2}!|9#####|'
3030 |L1|97|97|94|98|92|2.|21>| |→α_↓|9|9|1|93|95|94|99|96|94>
3032 {B2}!|9#######|'|L1|94|91|99|98|95|97>|L!!!!!!!|εAnswer|*/:|\
3034 (1419857)|β1|β0.>{A9}|π!|9|7A reasonably good
3039 check on the computations may be had by ``casting
3048 out mines'': The sum of the digits of the decimal
3058 number must equal the alternating sum and di=erence
3066 of the digits of the octal number, with the rightmost
3076 digit of the latter given a plus sign, except
3085 for a multiple of nine. In the above example,
3094 we have 1|4α+↓|44|4α+↓|41|4α+↓|49|4α+↓|48|4α+↓|45|4α+↓|47|4α
3096 =↓|435, and 1|4α_↓|42|4α+↓|41|4α_↓|45|4α+↓|42|4α_↓|43|4α+↓|4
3098 5|4α=↓|4|→α_↓1, and the di=erence is 36 (a multiple
3106 of 9). If this test fails, it can be applied
3116 to the |εk|4α+↓|41 |πleading digits after the
3123 |εk|πth step, and the error can be located using
3132 a ``binary search'' procedure; i.e., start by
3139 checking the middle result, then use the same
3147 procedure on the _rst or second half of the calculation,
3157 depending on whether the middle result is incorrect
3165 or correct.|'!|9|7Of course, the ``casting-out-nines''
3171 process is only about 89 percent reliable; !|9|7Of
3179 course, the ``casting-out-nines'' process is
3184 only about 89 percent reliable; an even better
3192 check is to convert the answer back to octal
3201 by using an inverse method, which we will now
3210 consider.|'{A12}|εConverting decimal integers
3214 to octal.|9|4|πA similar procedure can be used
3221 for the opposite conversion: Write down the given
3229 decimal number; at the |εk|πth |πstep, double
3236 the |εk |πleading digits using |εoctal |πarithmetic,
3243 and |εadd |πthese to the |εk|4α+↓|41 |πleading
3250 digits using |εoctal |πarithmetic. The process
3256 terminates in |εn|4α_↓|41 |πsteps if the given
3263 number has |εn |πdigits.|'{A6}|≡E|≡x|≡a|≡m|≡p|≡l|≡e
3268 |≡2|≡.|9|4Convert (1419857)|β1|β0 to octal.|'
3272 {A6}!!!!!!!!|∂1|2.}24|91|99|98|95|97|'|L!|12>
3274 {B2}|L##>|L1|96|2.|21|99|98|95|97>|L!|13|94>{B2}!!!!!!!!###|
3277 '|L2|91|95|2.|29|98|95|97>|L!|14|93|92>{B2}!!!!!!!!####|'
3281 |L2|96|91|93|2.|28|95|97>|L!|15|94|92|96>{B2}!!!!!!!!####|'
3284 |L3|93|95|96|96|2.|25|97>|L!|16|97|93|95|94>!!!!!!!!#####|'
3287 |L4|92|95|92|94|91|2.|27>|L1|90|95|92|95|90|92>
3289 {B2}!!!!!!!!######|'|L5|93|92|95|91|92|91>{A6}{M13}(Note
3292 that the nonoctal digits 8 and 9 center into
3301 this octal cmputation.) The answer can be checked
3309 as discussed above. This method was published
3316 by Charles P. Rozier, |εIEEE Trans. |π|≡C|≡E|≡-|≡1|≡1
3323 (1962), 708<709.|'{A60}|εAnswer|*/:|\ (5325121)|β8.|'
3327 {A9}{H10L12M29}!|9|7|πThe two procedures just
3331 given are essentially Method (1b) of the general
3339 radix conversion procedures. Doubling and subtracting
3345 in decimal notation is like multiplying by 10|4α_↓|42|4α=↓|4
3352 8; doubling and adding in octal notation is like
3361 multiplying by 8|4α+↓|42|4α=↓|410. There is a
3367 similar method for hexadecimal/decimal conversions,
3372 but it is a little more di∃cult since it involves
3382 multiplication by 6 instead of by 2.|'!|9|7To
3390 keep these two methods straingt in our minds,
3398 it is not hard to remember that we must subtract
3408 to go fr{U0}{H10L12M29}|π58320#Computer Programming!(Knuth/A
folio 407 galley 3
3411 ddison-Wesley)!f. 407!ch. 4!g. 3(c)|'{A12}|εConverting
3416 fractions.|9|4|πNo equally fast method of converting
3422 fractions manually is known; the best way seems
3430 to be Method (2a), with doubling and adding or
3439 subtracting to simplify the multiplications by
3445 10 or by 8. In this case, we reverse the addition-subtractio
3455 n criterion, adding when we convert to decimal
3463 and subtracting when we convert to octal; we
3471 also use the radix of the given input number,
3480 |εnot |πthe radix of the answer, in this computation
3489 (see Examples 3 and 4). The process is about
3498 twice as hard as the above method for integers.|'
3507 {A12}{M11.6}|≡E|≡x|≡a|≡m|≡p|≡l|≡e |≡3|≡.|9|4Convert
3509 (.14159)|β1|β0 to octal.|'{A6}.|21|94|91|95|99|'
3513 |7!|12|98|93|91|98|→α_↓|'{B2}#####|'|71|2.|21|93|92|97|92|'
3516 |7|9|1|9!|12|96|95|94|94|→α_↓|'{B2}!|9#####|'
3518 !|4|41|2.|20|96|91|97|96|'!!!|11|92|93|95|92|→#|'
3520 {B2}!!|9#####|'!!|90|2.|24|99|94|90|98|'!!!!|99|98|98|91|96|
3522 →α_↓|'{B2}!!!|9|1#####|'!!!|9|13|2.|29|95|92|94|96|'
3525 !!!|9|1!|11|99|90|95|92|98|→α_↓|'{B2}!!!!|9|2#####|'
3527 !!!!|9|27|2.|26|92|91|91|92|'!!!!|9|2!|11|92|94|92|92|94|→α_
3528 ↓|'!!!!|9|2!|1#####|'!!!!!|9|34|2.|29|96|98|99|96|'
3531 {A6}|εAnswer|*/:|\|9(.110374|4.|4.|4.)|β8.|'{A6}|π|≡E|≡x|≡a|≡
3532 m|≡p|≡l|≡e |≡4|≡.|9|4Convert (.110374)|β8 to
3536 decimal.|'{A6}.|21|91|90|93|97|94|'!|4|42|92|90|97|97|90|→α+
3538 ↓|'{B2}|7#####|'|71|2.|23|92|94|97|93|90|'!!|26|95|91|96|96|
3541 90|→α+↓|'{B2}!|4|4######|'!|4|44|2.|21|92|91|91|96|90|'
3544 !!!|32|94|92|93|94|90|→α+↓|'{B2}!!|2######|'!!|21|2.|24|95|9
3546 4|91|94|90|'!!!|31|91|93|90|93|90|90|→α+↓|'{B2}!!!|3#######|
3548 '!!!|35|2.|26|97|91|97|90|90|'!!!!|9|1|41|95|96|93|96|90|90|
3550 →α+↓|'{B2}!!!!|9|1|4#######|'!!!!|9|1|48|2.|25|90|92|96|90|9
3552 0|'!!!!!|9|1|51|92|90|95|94|90|90|→α+↓|'{B2}!!!!!|9|1|5#####
3554 ##|'!!!!!|9|1|56|2.|22|93|93|94|90|90|'{A6}|εAnswer|*/:|\
3557 (.141586|4.|4.|4.)|β1|β0.|'{H10L12M29}{B2}|J#>
3559 {A6}|π|≡D|≡.|9|≡F|≡l|≡o|≡a|≡t|≡i|≡n|≡g|≡-|≡p|≡o|≡i|≡n|≡t
3560 |≡c|≡o|≡n|≡v|≡e|≡r|≡s|≡i|≡o|≡n|≡.|9|4When ⊗oating-point
3562 values are to be converted, it is necessary to
3571 deal with both the exponent and the fraction
3579 parts simultaneously, since conversion of the
3585 exponent will a=ect the fraction part. Given
3592 the number |εf|4|¬O|42|ge |πto be converted to
3599 decimal, we may express |ε2|ge |πin the form
3607 |εF|4|¬O|410|gE |π(usually by means of auxiliar
3613 tables), and then convert |εFf |πto decimal.
3620 Alternatively, we can multiply |εe |πby log|β1|β0|42
3627 and round this to the nearest integer |εE; |πthen
3636 divide |εf|4|¬O|42|ge |πby 10|ε|gE |πand convert
3642 the result. Conversely, given the number |εF|4|¬O|410|gE
3649 |πto be converted to binary, we may convert |εF
3658 |πand then multiply it by the ⊗oating-point number
3666 10|ε|gE |π(again commonly obtained by using tables).
3673 Obvious techniques may be used to reduce the
3681 maximum size of the auxiliary tables by using
3689 several multiplications and/or divisions, although
3694 this can cause rounding errors to propagate.|'
3701 {A12}|≡E|≡.|9|≡M|≡u|≡l|≡t|≡i|≡p|≡l|≡e|≡-|≡p|≡r|≡e|≡c|≡i|≡s|≡
3701 i|≡o|≡n |≡c|≡o|≡n|≡v|≡e|≡r|≡s|≡i|≡o|≡.|9|4When
3703 converting multiple-precision numbers, it is
3708 most convenient to start by converting blocks
3715 of digits, which can be handled by singe-precision
3723 techniques, then to combine them using simple
3730 multiple-precision techniques. For example, suppose
3735 that 10|ε|gn |πis the highest power of 10 less
3744 than the computer word size. Then|'{A12}|π!|9|7a)|9To
3751 convert a multiple-precision |εinteger |πfrom
3756 binary to decimal, divide repeatedly by 10|ε|gn
3763 |π(thus converting from binary to radix 10|ε|gn
3770 |πby Method (1a)). Single-precision operations
3775 will give the |εn |πdecimal digits for each place
3784 of the radix 10|ε|gn |πrepresentation.|'!|9|7b)|9To
3790 convert a multiple-precision |εfraction |πfrom
3795 binary to decimal, proceed similarly, multiplying
3801 by 10|ε|gn |π(i.e., using Method (2a) with |εB|4α=↓|410|gn).
3808 |'|π!|9|7c)|9To convert a multiple-precision
3813 integer from decimal to binary, convert blocks
3820 of |εn |πdigits _rst; then convert from radix
3828 10|ε|gn |πto binary by using Method (1b).|'!|9|7d)|9Finally,
3835 a multiple-precision fraction may be converted
3842 from decimal to binary by a technique similar
3850 to (c), using Method (2b).|'{A12}|≡F|≡.|9|≡H|≡i|≡s|≡t|≡o|≡r|
3855 ≡y |≡a|≡n|≡d |≡B|≡i|≡b|≡l|≡i|≡o|≡g|≡r|≡a|≡p|≡h|≡y|≡.|9|4Radi
3857 x conversion techniques implicitly originated
3862 in ancient problems dealing with weights, measures,
3869 and currencies, when a mixed radix system was
3877 generally involved. Auxiliary tables were usually
3883 used as an aid to conversion. During the seventeenth
3892 century when sexagesimal fractions were being
3898 supplanted by decimal fractions, it was necessary
3905 to convert between the two systems in order to
3914 use existing books of tables; a systematic method
3922 to transform fractions from radix 60 to radix
3930 10 and vice versa was given in the 1667 edition
3940 of William Oughtred's |εClavis Mathematic|9|4,
3945 |πChapter 6, Section 18. (This material was not
3953 present in the original 1631 edition of Oughtred's
3961 book.) Conversion rules had been given already
3968 by al-Kash|=7↓|Z of Persia in his |εkey to Arithmetic
3977 |π(c. 1414), where Methods (1a), (1b), and (2a)
3985 are clearly explained |ε[Istoriko-Mat. Issled.
3990 |≡7 (1954), 126<135], |πbut his work was unknown
3998 in Europe. The 18th century American mathematician
4005 Hugh Jones used the words ``octavation'' and
4012 ``decimation'' to describe octal/decimal conversions,
4017 but his methods were not as clever as his terminology.
4027 A. M. Legendre [|εTh|=1eorie des nombres |π(Paris,
4034 1798), 229] noted that positive integers may
4041 be conveniently converted to binary form by repeatedly
4049 dividing by 64.|'!|9|7In 1946, H. H. Goldstine
4057 and J. von Neumann gave prominent consideration
4064 to radix conversion in their classic memoir,
4071 ``Planning and coding problems for an electronic
4078 computing instrument,'' because it was necessary
4084 to justify the use of binary arithmetic; see
4092 John von Neumann, |εCollected Works |≡5 |π(New
4099 York: Macmillan, 1963), 127<142. Another early
4105 discussion of radix conversion on binary computers
4112 was published by F. Koons and S. Lubkin, |εMath.
4121 Comp. |≡3 |π(1949), 427<431, where a rather unusual
4129 method is suggested. The _rst discussion of ⊗oating-point
4137 conversion was given somewhat later by F. L.
4145 Bauer and K. Samelson |ε[Zeit. f|=4ur angewandte
4152 Math. und Physik |≡4 |π(1953), 312<316].|'!|9|7The
4159 following articles may be useful for further
4166 reference: A note by G. T. Lake |ε[CACM |≡5 |π(1962),
4176 468<469] mentions some hardware techniques for
4182 conversion and gives clear examples. A. H. Stroud
4190 and D. Secrest |ε[Comp. J. |≡6 |π(1963), 62<66]
4198 have discussed conversion of multiple-precision
4203 ⊗oating-point numbers. The conversion of |εunnormalized
4209 |π⊗oating-point numbers, preserving the amount
4214 of ``signi_cance'' implied by the representation,
4220 has been discussed by H. Kanner |ε[JACM |≡1|≡2
4228 (1965), 242<246] |πand by N. Metropolis and R.
4236 L. Ashenhurst |ε[Math. Comp |≡1|≡9 (1965), 435<441].
4243 |πSee also K. Sikdar, |εSankhy|=3a |π|≡3|≡0|≡B
4249 (1968), 315<334, and the references he cites.|'
4256 {A24}|*/|\|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'{A11}{H9L11}|9|1|≡1|≡.
4257 |9|4[|*/|↔P|↔C|\] Generalize Method (1b) so that
4263 it works with mixed-radix notations, converting|'
4269 {A9}|εa|βmb|βm|βα_↓|β1|4.|4.|4.|4b|β1b|β0|4α+↓|4|¬O|4|¬O|4|¬
4269 O|4α+↓|4a|β1b|β0|4α+↓|4a|β0!|πinto!|εA|βMB|βM|βα_↓|β1|4.|4.|
4269 4.|4B|β1B|β0|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4A|β1B|β0|4α+↓|4A|β0,|
4269 ;{A9}|πwhere 0|4|¬E|4|εa|βj|4|¬W|4b|βj, 0|4|¬E|4A|βJ|4|¬W|4B
4272 |βJ |πfor |ε0|4|¬E|4j|4|¬W|4m, 0|4|¬E|4J|4|¬W|4M.|'
4276 |π!!|2Give an example of your generalization
4282 by manually converting the quantity ``3 days,
4289 9 hours, 12 minutes, and 37 seconds'' into long
4298 tons, hundredweights, stones, pounds, and ounces.
4304 (Let one second equal one ounce. The British
4312 system of weights has 1 stone|4α=↓|414 pounds,
4319 1 hundredweight|4α=↓|48 stone, 1 long ton|4α=↓|420
4325 hundredweight.) In other words, let |εb|β0|4α=↓|460,
4331 b|β1|4α=↓|460, b|β2|4α=↓|424, m|4α=↓|43, B|β0|4α=↓|416,
4335 B|β1|4α=↓|414, B|β2|4α=↓|48, B|β3|4α=↓|420, M|4α=↓|44;
4339 |πthe problem is to _nd |εA|β4,|4.|4.|4.|4, A|β0
4346 |πin the proper ranges such that |ε3b|β2b|β1b|β0|4α+↓|42b|β1
4352 b|β0|4α+↓|412b|β0|4α+↓|437|4α=↓|4A|β4B|β3B|β2B|β1B|β0|4α+↓|4
4352 A|β3B|β2B|β1B|β0|4α+↓|4A|β2B|β1B|β0|4α+↓|4A|β1B|β0|4α+↓|4A|β
4352 0, |πusing a systematic method which generalizes
4359 Method (1b). (All arithmetic is to be done in
4368 a mixed-radix system.)|'{A3}|9|1|≡2|≡.|9|4[|*/|↔P|↔C|\]
4372 Generalize Method (1a) so that it works with
4380 mixed-radix notations, as in exercise 1, and
4387 give an example of your generalization by manually
4395 solving the same conversion problem stated in
4402 exercise 1.|'{A3}|9|1|≡3|≡.|9|4[|*/|↔P|↔C|\] (D.
4406 Taranto.) The text observes that when fractions
4413 are bing converted, there is in general no obvious
4422 way to decide how many digbits to give in the
4432 answer. Design a simple generalization of Method
4439 (2a) which, given two positive radix |εb |πfractions
4447 |εu |πand |ε|≤o |πbetween 0 and 1, converts |εu
4456 |πto a radix |εB |πequivalent |εU |πwhich has
4464 just enouth places of accuracy to ensure that
4472 |ε|¬GU|4α_↓|4u|¬G|4|¬W|4|≤o. |π(If |εu|4|¬W|4|≤o,
4475 |πwe may take |εU|4α=↓|40, |πwith zero ``places
4482 of accuracy.'')|'{A3}|9|1|≡4|≡.|9|4[|εM|π|*/|↔P|↔O|\]
4485 (a) Prove that every real number which has a
4494 terminating |εbinary |πrepresentation also has
4499 a terminating |εdecimal |πrepresentation. (b)
4504 Find a simpl condition on the positive integers
4512 |εb |πand |εB, |πwhich is satis_ed if and only
4521 if every real number which has a teminatiing
4529 radix |εb |πrepresentation also has a terminating
4536 radix |εB |πrepresentation.|'{A3}|9|1|≡5|≡.|9|4[|εM|π|*/|↔P|↔
4539 c|\] Show that program (4) would work also if
4548 the instruction ``|¬l|¬d|¬x|≤$|¬1|¬0|g|¬n|≤$''
4551 were replaced by ``|¬l|¬d|¬x |≤$|εc|≤$'' |πfor
4557 certain other constants |εc.|'{A3}|9|1|π|≡6|≡.|9|4[|*/|↔L|↔c|
4561 \] Discuss using Methods (1a), (1b), (2a), and
4569 (2b) when |εb |πor |εB |πis |→α_↓2.|'{A3}|9|1|≡7|≡.|9|4[|εM|
4576 π|*/|↔O|↔l|\] Given that 0|4|¬W|4|ε|≤a|4|¬E|4x|4|¬E|4|≤a|4α+↓
4579 |41/w |πand 0|4|¬E|4|εu|4|¬E|4w, |πprove that
4584 |"l|εux|"L|4α=↓|4|"l|≤au|"L |πor |ε|"l|≤au|"L|4α+↓|41.
4587 |πFurthermore |ε|"lux|"L|4α=↓|4|"l|≤ax|"L |πexactly,
4590 if |εu|4|¬W|4|≤aw |πand |ε|≤a|gα_↓|g1 |πis an
4596 integer.|'{A3}|9|1|≡8|≡.|9|4[|*/|↔P|↔M|\] Write
4599 a |¬m|¬i|¬x program analogous to (1) which uses
4607 (5) and which does not include any division instructions.|'
4616 {A3}|9|1|≡9|≡.|9|4[|εM|π|*/|↔P|↔p|\] Let |εu |πbe
4620 an integer, 0|4|¬E|4|εu|4|¬W|42|g3|g4. |πAssume
4624 that the following sequence of operations (equivalent
4631 to addition and binary ``shift-right'' instructions)
4637 is performed:|'{A6}|h|ε|∂v|4|¬L|4v|4α+↓|4|"l2|gα_↓|g8v|"L,!!
4639 |∂v|4|¬L|4v|4α+↓|4|"l2|gα_↓|g1|g6v|"L,!!|∂v|4|¬L|4v|4α+↓|4|"
4639 l2|gα_↓|g4v|"L,|E|n|;|Lv|4|¬L|4|"l|f1|d32|)u|"L,|Lv|4|¬L|4v|
4640 4α+↓|4|"l|f1|d32|)|"L,|Lv|4|¬L|4v|4α+↓|4|"l2|gα_↓|g4v|"L,>
4641 {A4}|Lv|4|¬L|4v|4α+↓|4|"l2|gα_↓|g8v|"L,|Lv|4|¬L|4v|4α+↓|4|"l
4641 2|gα_↓|g1|g6v|"L,|Lv|4|¬L|4|"l|f1|d38|)v|"L.>
4642 {A6}|πProve that |εv|4α=↓|4|"lu/10|"L |πor |ε|"lu/10|"L|4α_↓
4646 |41.|'{A3}|π|≡1|≡0|≡.|9|4[|*/|↔P|↔P|\] The text
4650 shows how a binary-coded decimal number can be
4658 doubled by using various shifting, extracting,
4664 and addition operations on a binary computer.
4671 Give an analogous method which computes |εhalf
4678 |πof a binary-coded decimal number (throwing
4684 away the remainder if the number is odd).|'|Hβ*?*?*?*!*!*!*!*!*!*!*!*!*!*!
4692
folio 411 galley 4
{U0}{H10L12M29}|π58320#Computer Programming!(Knuth/Ad
1041 dison-Wesley)!f. 411!ch. 4!g. 4c|'{A6}|≡1|≡1|≡.|9|4[|*/|↔O|↔o
1045 |\] Convert (57721)|β8 to decimal.|'{A3}|≡1|≡2|≡.|9|4[|*/|↔P|
1050 ↔P|\] Invent a rapid pencil-and-paper method
1056 for converting integers from ternary notation
1062 to decimal, and illustrate your method by converting
1070 (1212011210210)|β3 into decimal. How would you
1076 go fromdecimal to ternary?|'{A3}|≡1|≡3|≡.|9|4[|*/|↔P|↔C|\]
1081 Assume that locations |¬u|4α+↓|41, |¬u|4α+↓|42,|4.|4.|4.|4,
1086 |¬u|4α+↓|4|εm |πcontain a multiple-precision
1090 fraction |ε(.u|βα_↓|β1u|βα_↓|β2|4.|4.|4.|4j|βα_↓|βm)|βb,
1092 |πwhere |εb |πis the word size of |¬m|¬i|¬x|¬.
1100 Write a |¬m|¬i|¬x routine which converts this
1107 fraction to decimal notation, truncating it to
1114 180 decimal digits. The answer should be printed
1122 on two lines, with the digits grouped into 20
1131 blocks of nine each separated by blanks. (Use
1139 the |¬c|¬h|¬a|¬r instruction.)|'{A3}|≡1|≡4|≡.|9|4[|εM|π|*/|↔P
1142 |↔p|\] (A. Sch|=4onhage.) The text's method of
1149 converting multiple-precision integers requires
1153 an execution time of order |εn|g2 |πto convert
1161 an |εn-|πdigit integer, when |εn |πis large.
1168 Show that it is possible to convert |εn-|πdigit
1176 decimal integers into binary notation in |εO{H11}({H9}M(n)|π
1182 log|4|εn{H11}){H9} |πcycles, where |εM(n) |πis
1187 an upper bound on the number of cycles needed
1196 to multiply |εn-|πbit binary numbers which represents
1203 the best |εp-|πdigit base |εb |π⊗oating-point
1209 approximation to |εu, |πin the sense of Section
1217 4.2.2. Under the assumption that log|ε|βB|4b
1223 |πis irrational and that the range of exponents
1231 is unlimited, prove that |'{A9}|εu|4α=↓|4|πround|ε|βb{H11}({
1236 H9}|πround|ε|βB(u,|4P),|4p{H11}){H9},|;{A9}|πfor
1238 all |εp-|πdigit base |εb |π⊗oating-point numbers
1244 |εu, |πif and only if |εB|gp|gα_↓|g1|4|¬R|4b|gp.
1250 |π(In othert words, an ``ideal'' input conversion
1257 of |εu |πinto an independent base |εB, |πfollowed
1265 by an ``ideal'' output conversion of this result,
1273 will always yield |εu |πagain if and only if
1282 the intermediate precision |εP |πis suitably
1288 large, as speci_ed by the formula above.)|'{A3}|≡1|≡9|≡.|9|4
1295 [|εM|π|*/|↔P|↔L|\] Let the decimal number |εu|4α=↓|4(u|β7|4.|
1300 4.|4.|4u|β1u|β0)|β1|β0 |πbe represented as the
1305 binary-coded decimal number |εU|4α=↓|4(u|β7|4.|4.|4.|4u|β1u|
1308 β0)|β1|β6. |πFind appropriate constants |εc|βi
1313 |πand masks |εm|βi |πso that the operation |εU|4|¬L|4U|4α_↓|
1320 4c|βi(U|4|↔i|4m|βi), |πrepeated for |εi|4α=↓|41,
1324 2, 3, |πwill convert |εU |πto the binary representation
1333 of |εu, |πwhere ``|→|↔i'' |πdenotes extraction
1339 (i.e., ``logical |¬a|¬n|¬d'' on individual bits).|'
1345 {A25}{H10L12}|∨4|∨.|∨5|∨.|9|∨R|∨A|∨T|∨I|∨O|∨N|∨A|∨L|9|∨A|∨R|
1345 ∨I|∨T|∨H|∨M|∨E|∨T|∨I|∨C|'{A12}|∨4|∨.|∨5|∨.|∨1|∨.|9|∨F|∨r|∨a|
1346 ∨c|∨t|∨i|∨o|∨n|∨s|'{A6}In many numerical algorithms
1351 it is important to know that the answer to a
1361 problem is exactly |f1|d33|), not a ⊗oating-point
1368 number which gets printed as ``0.333333574''.
1374 If arithmetic is done on fractions instead of
1382 on approximations to fractions, many computations
1388 can be done entirely |εwithout any accumulated
1395 rounding errors. |πThis results in a comfortable
1402 feeling of security which is often lacking when
1410 ⊗oating-point calculations have been made, and
1416 it means that the accuracy of the calculation
1424 cannot be improved upon.|'!|9|7When fractional
1430 arithmetic is desired, th e numbers can be represented
1439 as pairs of integers, |ε(u/u|¬S), |πwhere |εu
1446 |πand |εu|¬S |πare relatively prime to each other
1454 and |εu|¬S|4|¬Q|40. |πThe number zero is represented
1461 as (o/1). In this form, |ε(u/u|¬S)|4α=↓|4(v/v|¬S)
1467 |πif and only if |εu|4α=↓|4v| |πand |εu|¬S|4α=↓|4v|¬S.|'
1473 |π!|9|7Multiplication of fractions is, of course,
1479 rather simple; to form |ε(u/u|¬S)|4α⊗↓|4(v/v|¬S)|4α=↓|4(w/w|
1483 ¬S), |πwe can simply compute |εuv |πand |εu|¬Sv|¬S.
1491 |πThe two products |εuv |πand |εu|¬Sv|¬S |πmight
1498 not be relatively prime, but if |εd|4α=↓|4|πgcd|ε(uv,|4u|¬Sv
1504 |¬S), |πthe desired answer is |εw|4α=↓|4uv/d,
1510 w|¬Sα=↓u|¬Sv|¬S/d. |π(See exercise 2.) E∃cient
1515 algorithms to compute the greatest common divisor
1522 are discussed in Section 4.5.2.|'!|9|7Another
1528 way to perform the multiplication is to _nd |εd|β1|4α=↓|4|πg
1536 cd|ε(u,|4v|¬S) |πand |εd|β2|4α=↓|4|πgcd|ε(u|¬S,|4v);
1539 |πthen the answer is |εw|4α=↓|4(u/d|β1)(v/d|β2),
1544 w|¬S|4α=↓|4(u|¬S/d|β2)(v|¬S/d|β1). |π(See exercise
1547 3.) This method requires two gcd calculations,
1554 but it is not really slower than the former method;
1564 the gcd process involves a number of iterations
1572 essentially proportional to the logarithm of
1578 its inputs, so the total number of iterations
1586 needed to evaluate both |εd|β1 |πand |εd|β2 |πis
1594 essentially the same as the number of iterations
1602 during the single calculation of |εd. |πFurthermore,
1609 each iteration in the elevation of |εd|β1 |πand
1617 |εd|β2 |πis potentially faster, because comparatively
1623 small numbers are being examined. If |εu, u|¬S,
1631 v, v|¬S |πare single-precision quantities, this
1637 method hs the advantagbe that no double-precision
1644 numbers appear in the calculation unless it is
1652 impossible to represent both of the answers |εw
1660 |πand |εw|¬S |πin single precision form.|'!|9|7Division
1667 may be done in a similar manner; see exercise
1676 4.|'!|9|7Addition and subtraction are slightly
1682 more complicated. We can set |ε(u/u|¬S)|4|¬N|4(v/v|¬S)|4α=↓|
1687 4{H12}({H10}(uv|¬S|4|¬N|4u|¬Sv)/u|¬Sv|¬S{H12}){H10}
1688 |πand reduce this fraction to lowest terms by
1696 calculating |εd|4α=↓|4|πgcd|ε(uv|¬S|4|¬N|4u|¬Sv,|4u|¬Sv|¬S)
1698 |πas in the _rst multiplication method. But again
1706 it is possible to avoid working with such large
1715 numbers, if we start by calculating |εd|β1|4α=↓|4|πgcd|ε(u|¬
1721 S,|4v|¬S). |πIf |εd|β1|4α=↓|41 |πthen |εw|4α=↓|4uv|¬S|4|¬N|4
1725 u|¬Sv |πand |εw|¬S|4α=↓|4|¬Sv|¬S |πare the desired
1731 answers. (According to THhe*? fraction to lowest
1738 terms by calculating |εd|4α=↓|4|πgcd|ε(uv|¬S|4|¬N|4u|¬Sv,|4u
1741 |¬Sv|¬S) |πas in the _rst multiplication method.
1748 But again it is possible to avoid working with
1757 such large numbers, if we start by calculating
1765 |εd|β1|4α=↓|4|πgcd|ε(u|¬S,|4v|¬S). |πIf |εd|β1|4α=↓|41
1768 |πthen |εw|4α=↓|4uv|¬S|4|¬N|4u|¬Sv |πand |εw|¬S|4α=↓|4|¬Sv|¬
1771 S |πare the desired answers. (According to Theorem
1779 4.5.2D, |εd|β1 |πwill be 1 about 61 percent of
1788 the time, if the denominators |εu|¬S |πand |εv|¬S
1796 |πare randomly distributed, so it is wise to
1804 single out this case separately.) If |εd|β1|4|¬Q|41,
1811 |πthen let |εt|4α=↓|4u(v|¬S/d|β1)|¬N|4v(u|¬S/d|β1)
1814 |πand calclate |εd|β2|4α=↓|4|πgcd|ε(t,|4d|β1);
1817 |π_nally the answer is |εw|4α=↓|4t/d|β2, w|¬S|4α=↓|4(u|¬S/d|
1822 β1)(v|¬S/d|β2). (|πExercise 6 proves that these
1828 values of |εw |πand |εw|¬S |πare relatively prime
1836 to each other.) If single-precision numbers are
1843 being used, this method requires only single-precision
1850 operations, except that |εt |πmay be a double-precision
1858 number or slightly larger (see exercise 7); since
1866 gcd|ε(t,|4d|β1)|4α=↓|4|πgcd(|εt|4|πmod|4|εd|β1,|4d|β1),
1867 |πthe calculation of |εd|β2 |πdoes not require
1874 double precision.|'!|9|7For example, to compute
1880 (7/66)|4α+↓|4(17/12), we form |εd|β1|4α=↓|4|πgcd(66,|412)|4α
1883 =↓|46; then |εt|4α=↓|47|4|¬O|42|4α+↓|417|4|¬O|411|4α=↓|4201,
1885 |πand |εd|β2|4α=↓|4|πgcd(201,|46)|4α=↓|43, so
1889 the answer is|'{A9}|f201|d33|)/|f66|d36|)|4|f12|d33|)|4α=↓|4
1892 67/44.|'{A9}!|9|7Experience with fractional calculations
1897 shows that in many cases the numbers grow to
1906 be quite large; for example, see the remarks
1914 following Eq. 3.3.2<22. So if |εu |πand |εu|¬S
1922 |πare intended to be single-precision numbers
1928 for each fraction |ε(u/u|¬S), |πit is important
1935 to include tests for over⊗ow in each of the addition,
1945 subtraction, multiplication, and division subroutines.
1950 For numerical problems in which perfect accuracy
1957 is important, a set of subroutines for fractional
1965 arithmetic with |εarbitrary |πprecision allowed
1970 in numerator and denominator is very useful.|'
1977 !|9|7The methods of this section also extend
1984 to other number _elds besides the rational numbers;
1992 for example, we could do arithmetic on quantities
2000 of the form |ε(u|4α+↓|4u|¬S{H11}|¬H{H10}|v45)u|¬C,
2004 |πwhere |εu, u|¬S, u|¬C |πare integers, gcd|ε(u,|4u|¬S,|4u|¬
2010 C)|4α=↓|41, |πand |εu|¬C|4|¬Q|40; |πor on quantities
2016 of the form |ε(u|4α+↓|4u|¬S|=|g3{H11}|¬H{H10}|v42|)|4α+↓|4u|
2019 ¬C|=|g3{H11}|¬H{H10}|v44|))/u|9|1, |πetc.|'!|9|7To
2022 help check out subroutines for rational arithmetic,
2029 inversion of matrices with known inverses (e.g.,
2036 Cauchy matrices, exercises 111111*?*?!|9|7To help
2041 check out subroutines for rational arithmetic,
2047 inversion of matrices with known inverses (e.g.,
2054 Cauchy matrices, exercise 1.2.3<41) is suggested.|'
2060 !|9|7Exacty representation of fractions within
2065 a computer was _rst discussed in the literature
2073 by P. Henrici, |εJACM |≡3 (1956), 6<9.|'{A24}|π|∨E|∨X|∨E|∨R|
2080 ∨C|∨I|∨S|∨E|∨S|'{A12}{H9L11}|9|1|≡1|≡.|9|4[|*/|↔O|↔C|\]
2082 Suggest a reasonable computational method for
2088 comparing two fractions, to test whether or not
2096 |ε(u/u|¬S)|4|¬W|4(v/v|¬S).|'{A3}|π|9|1|≡2|≡.|9|4[|εM|π|*/|↔O|
2097 ↔C|\] Prove that if |εd|4α=↓|4|πgcd|ε(u,|4v)
2102 |πthen |εu/d |πand |εv/d |πare relatively prime.|'
2109 {A3}|9|1|≡3|≡.|9|4[|εM|π|*/|↔P|↔c|\] Prove that
2112 if |εu |πand |εu|¬S |πare relatively prime, and
2120 if |εv |πand |εv|¬S |πare relatively prime, then
2128 gcd(|εuv,|4u|¬Sv|¬S)|4α=↓|4|πgcd|ε(u,|4v|¬S)|πgcd|ε(u|¬S,|4v
2128 ).|'{A3}|9|1|π|≡4|≡.|9|4|*/|↔O|↔O|\] Design a
2132 division algorithm for fractions, analogous to
2138 the second multiplication method of the text.
2145 (Note that the sign of |ε|≤v |πmust be considered.)|'
2154 {A3}|9|1|≡5|≡.|9|4[|*/|↔O|↔c|\] Compute (17/120)|4α+↓|4(|→α_↓
2156 27/70) by the method recommended in the text.|'
2164 {A3}|9|1|≡6|≡.|9|4[|εM|π|*/|↔P|↔L|\] Show that
2167 if |εu, u|¬S |πare relatively prime and if |εv,
2176 v|¬S |πare relatively prime, then gcd(|εuv|¬S|4α+↓|4vu|¬S,|4
2181 u|¬Sv|¬S)|4α=↓|4d|β1d|β2 |πwhere |εd|β1|4α=↓|4|πgcd|ε(u|¬S,|
2183 4v|¬S) |πand |εd|β2|4α=↓|4|πgcd(|εd|β1,|4u(v|¬S/d|β1)|4α+↓|4
2185 v(u|¬S/d|β1)). |π(Hence if |εd|β1|4α=↓|41, |πthenn
2190 |εεεεεε*?*?|¬S/d|β1)). |π(Hence if |εd|β1|4α=↓|41,
2194 |πthen |εuv|¬S|4α+↓|4vu|¬S |πis relatively prime
2199 to |εu|¬Sv|¬S.)|'{A3}|π|9|1|≡7|≡.|9|4[|εM|π|*/|↔P|↔P|\]
2202 How large can the absolute value of the quantity
2211 |εt |πbecome, in the addition-subtraction method
2217 recommended in the text, if the input numerators
2225 and denominators are less than |εN |πin absolute
2233 value?|'{A3}|9|1|≡8|≡.|9|4[|*/|↔P|↔P|\] Discuss
2236 using (1/0) and (|→α_↓1/0) |πas rep=resentations
2242 for |¬X and |→α_↓|¬X, and /or as representations
2250 of over⊗ow.|'{A3}|π|9|1|≡9|≡.|9|4[|εM|π|*/|↔P|↔L|\]
2253 If 1|4|¬E|4|εu|¬S, v|¬S|4|¬W|42|gn, |πshow that
2258 |"l2|ε|g2|gnu/u|¬S|"L|4α=↓|4|"l2|g2|gnv/v|¬S|"L
2259 |πimplies |εu/u|¬S|4α=↓|4v/v|¬S.|'{A3}|π|≡1|≡0|≡.|9|4|*/|\[|*/
2261 |↔M|↔O|\] Extend the subroutines suggested in
2267 exercise 4.3.1<34 so that they deal with ``arbitrary''
2275 rational numbers.|'{A3}|≡1|≡1|≡.|9|4[|εM|π|*/|↔P|↔L|\]
2278 Consider fractions of the form |ε(u|4α+↓|4u|¬S{H11}|¬H{H9}|v
2283 45|))/u|¬C, |πwhere |εu, u|¬S, u|¬C |πare integers,
2290 gcd(|εu,|4u|¬S,|4u|¬C)|4α=↓|41, |πand |εu|¬C|4|¬Q|40.
2293 |πExplain how to divide two such fractions and